package com.lw.leetcode.tree.a;

import com.lw.leetcode.tree.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 501. 二叉搜索树中的众数
 *
 * @Author liw
 * @Date 2021/5/10 17:36
 * @Version 1.0
 */
public class FindMode {

    public static void main(String[] args) {
        FindMode test = new FindMode();
        int[] mode = test.findMode(TreeNode.getInstance2());
        System.out.println(Arrays.toString(mode));
    }

    List<Integer> list = new ArrayList<>();
    int count = 0;
    int max = 0;
    int item = 0;

    public int[] findMode(TreeNode root) {
        find(root);
        int size = list.size();

        int[] arr = new int[size];
        for (int i = 0; i < size; ++i) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    public void find(TreeNode node) {
        if (node == null) {
            return;
        }
        find(node.left);
        int val = node.val;
        if (val == item) {
            count++;
        } else {
            item = val;
            count = 1;
        }
        if (count == max) {
            list.add(val);
        } else if (count > max) {
            max = count;
            list.clear();
            list.add(val);
        }
        find(node.right);
    }


}
